1. Field of the Invention
Aspects of the present invention relate to an optimized index-searching apparatus and method, and more particularly, to a search method and an optimized index-searching apparatus using an index that increases an efficiency of a storage space and provides various operations.
2. Description of the Related Art
Metadata-based user interfaces (UI) have become popular with the advances and increasing popularity of digital content technologies. Searching for content using only a folder and file name is difficult when there is a large amount of data. However, the metadata-based UI can change a search condition in order to search for content, and enables a user to easily remember the metadata value.
Specifically, in metadata-based browsing, a multi-level clustering-based UI enables a user to more conveniently understand the distribution of content, and efficiently access desired content by applying various search conditions. The multi-level clustering-based UI clusters content classified by level, and uses an index in order to move between the clusters.
Clustering refers to grouping similar objects. In the multi-level clustering, each cluster divided by the N th (N≧1) condition can be further divided into more detailed clusters by the (N+1)th condition. The content browser selects the clustering-based UI by dividing the entire content into a plurality of clusters by a predetermined condition, and then providing the divided content to a user.
FIG. 1 illustrates a schema of a table that stores image information. As shown in FIG. 1, there are fields 12 corresponding to information on a year, a month, and a day for each record of the table. Images managed by the table are clustered by each of three levels based on the year, the month, and the day fields 12 via the multi-level clustering-UI, and are then shown on a screen. The clusters of the lowest level (i.e., “day”) are ordered by title and displayed. To embody the multi-level clustering-UI, image records included in the cluster should be extracted from a database.
If photos included in 2006 (first level) May (second level) 1 (third level) are desired to be browsed, the records may be displayed on a screen through the following query: “Select*from Table where year=2006 and month=5 and day=1 order by title.”
When an inquiry including a predetermined condition for several fields (such as the above inquiry) is processed without a proper index, a longer time for processing the inquiry is needed according to an increase in the number of the image records. When an equal (=) is used in the query and there is a sorting condition for the lowest field, a multi-column B+ tree index is used. The multi-column B+ tree index combines the corresponding fields and uses them as a key of the index.
FIG. 2 depicts the structure of a multi-column B+ tree index 20. As shown in FIG. 2, if the multi-column B+ tree index 20 is used, when year, month, and day are selected as a specific value, entries of the index satisfying a predetermined condition are already arranged in a title order, and are adjacent to each other. Therefore, there is no additional arrangement cost that can reduce the time spent on the query.
The multi-column B+ tree index can be used when browsing a second level (month) or first level (year) instead of a third level (day). However, additional indexes are required (as shown in FIG. 3) because a longer time is needed for obtaining a cluster's name shown by each upper level using only the multi-column B+ tree index 20. To obtain clusters to be displayed on the first level using only the multi-column B+ tree index 20, all entries of the index should be read, which cannot satisfy the response time needed for an interactive screen configuration.
FIG. 3 depicts a multi-column B+ tree index for storing a multi-level cluster. As mentioned above, to reduce the response time, an additional index 30 is required in order to quickly search which value exists in the corresponding field. When a user wants to display the clusters configuring the first level, names of the first level clusters are used as an index. If a user wants to display records included in a predetermined cluster (e.g., a cluster corresponding to 2005), the multi-column B+ tree index successively reads records of 2005 (“year=2005”).
When clusters are browsed in the second level, the multi-column B+ tree index of “year, month” 40 is required in order to reduce the response time. When clusters are browsed in the third level, the multi-column B+ tree index of “year, month, day” 50 is required. If the number of fields that configure entire levels is N, the total number of the required multi-column B+ tree indexes is N. Accordingly, the first level key value is repeatedly stored in N indexes and the second level key value is stored in N−1 indexes, which causes a waste of storage space.